package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import org.apache.commons.lang3.time.StopWatch;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.TreeSet;

/**
 * @author Fengkai
 * @creat 2023/4/23
 * 存在一个 mn 的二维数组，其成员取值范围为 0 或 1。其中值为 1 的成员具备扩散性，每经过 1S，将上下左右值为 0 的成员同化为 1。
 * 二维数组的成员初始值都为 0，将第[i,j]和[k,l]两个个位置上元素修改成 1 后，求矩阵的所有元素变为 1 需要多长时间。
 * 输入描述:
 * 输出数据中的前 2 个数字表示这是一个 mn 的矩阵，m 和 n 不会超过 1024 大小；中间两个数字表示一个初始扩散点位置为 i,j；
 * 最后 2 个数字表示另一个扩散点位置为 k,l。
 * 输入描述:
 * 输出数据中的前 2 个数字表示这是一个 mn 的矩阵，m 和 n 不会超过 1024 大小；中间两个数字表示一个初始扩散点位置为 i,j；
 * 最后 2 个数字表示另一个扩散点位置为 k,l。
 * 输出描述:
 * 输出矩阵的所有元素变为 1 所需要秒数。
 */
public class JuZhenKuoSan {

    //我的更快
    public static void main (String[] args) {
        StopWatch stopWatch1 = new StopWatch();
        StopWatch stopWatch2 = new StopWatch();
        stopWatch1.start();
        System.out.println(getTime(10240, 10240, 0, 2, 3, 3));
        stopWatch1.stop();
        System.out.println(stopWatch1.getTime());

        stopWatch2.start();
        System.out.println(hisMethod(10240, 10240, 0, 2, 3, 3));
        stopWatch2.stop();
        System.out.println(stopWatch2.getTime());
    }

    public static int getTime (int m, int n, int x1, int y1, int x2, int y2) {
        int[] nums = new int[m * n];
        nums[x1 * m + y1] = 1;
        nums[x2 * m + y2] = 1;
        //数组中1的数量
        int oneCount = 2;
        int result = 0;
        ArrayList<int []> tochage = new ArrayList<>();
        tochage.add(new int[]{x1, y1});
        tochage.add(new int[]{x2, y2});
        //上下左右传播
        int[][] move = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        while (oneCount < m * n) {
            ArrayList<int []> cahce = new ArrayList<>();
            for (int[] split : tochage) {
                int x = split[0];
                int y = split[1];
                for (int[] moveIndex : move) {
                    int newX = x + moveIndex[0];
                    int newY = y + moveIndex[1];
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && nums[newX * n + newY] == 0) {
                        nums[newX * n + newY] = 1;
                        cahce.add(new int[]{newX, newY});
                        oneCount ++;
                    }
                }
            }
            tochage = cahce;
            result++;
        }
        return result;
    }


    public static int hisMethod (int m, int n, int x1, int y1, int x2, int y2) {
        int[][] array = new int[m][n];
        array[x1][y1] = 1;
        array[x2][y2] = 1;
        return  solveMethod(array, m, n);
    }

    private static int solveMethod (int[][] array, int m, int n) {
        int result = 0;
        while (isContainZero(array, m, n)) {
            int[][] arrayTemp = new int[m][n];
            for (int a = 0; a < m; ++a) {
                for (int b = 0; b < n; ++b) {
                    if (1 == array[a][b]) {
                        arrayTemp[a][b] = 1;
                        if (0 <= a - 1) {
                            arrayTemp[a - 1][b] = 1;
                        }
                        if (a + 1 < m) {
                            arrayTemp[a + 1][b] = 1;
                        }
                        if (b - 1 >= 0) {
                            arrayTemp[a][b - 1] = 1;
                        }
                        if (b + 1 < n) {
                            arrayTemp[a][b + 1] = 1;
                        }
                    }
                }
            }
            array = arrayTemp;
            result++;
        }
        return result;
    }

    public static boolean isContainZero (int[][] array, int m, int n) {
        for (int k = 0; k < m; k++) {
            for (int i = 0; i < n; i++) {
                if (array[k][i] == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}
